package top.hkyzf.study.leetcode.linkedlist;

import org.junit.Test;

/**
 * @author 朱峰
 * @date 2020-12-21 11:58
 */
public class 链表中倒数第k个节点_剑指Offer22 {

    ListNode head = new ListNode(0);

    // 添加节点
    public void add(ListNode node) {
        // 由于head节点不可移动，定义一个临时节点
        ListNode temp = head;
        while (true) {
            // 找到最后了
            if(temp.next == null) {
                break;
            }
            // 没有找到最后则temp后移继续循环
            temp = temp.next;
        }
        // 将新节点添加到链表最后
        temp.next = node;
    }

    // 列出链表所有元素
    public void list(ListNode listNode) {
        // 先判断链表是否为空
        if(listNode == null) {
            System.out.println("链表为空！");
            return;
        }
        // 不为空，开始遍历，由于head节点不可移动，定义一个临时节点
        ListNode temp = listNode;
        while (true) {
            // 先打印链表当前节点
            System.out.println(temp);
            // 判断下一节点是否为空，为空则遍历完毕，退出循环
            if(temp.next == null) {
                break;
            }
            // 有值则游标后移
            temp = temp.next;
        }
    }

    // 获取链表倒数第k个元素
    public ListNode getKthFromEnd(ListNode head, int k) {
        int length = 0;
        // 先判断链表是否为空，没有无效的头节点
        if(head == null) {
            System.out.println("链表为空！");
            return null;
        } else {
            // 不为空，开始遍历
            ListNode temp = head;
            while (true) {
                length++;
                // 判断下一节点是否为空，为空则遍历完毕，退出循环
                if (temp.next == null) {
                    break;
                }
                // 有值则游标后移
                temp = temp.next;
            }
        }
        if(k <= 0 || k > length) {
            System.out.println("输入不合法");
            return null;
        }
        ListNode temp = head;
        for(int i=0; i<(length-k); i++) {
            temp = temp.next;
        }
        return temp;
    }

    // 获取链表倒数第k个元素（看了评论，受了启发，快慢指针方式）
    public ListNode getKthFromEndByDoublePoint(ListNode head, int k) {
        ListNode fastNode = head;
        ListNode slowNode = head;
        boolean flag = false;
        while(fastNode != null) {
            fastNode = fastNode.next;
            k--;
            if(k<=0) {
                flag = true;
                break;
            }
        }
        // 走到了第k个，输入的k合法
        if(flag) {
            while (fastNode != null) {
                fastNode = fastNode.next;
                slowNode = slowNode.next;
            }
            list(slowNode);
            return slowNode;
        } else {
            System.out.println("输入的k不合法！");
            return null;
        }
    }

    @Test
    public void getKthFromEnd() {
        ListNode heroNode1 = new ListNode(1);
        ListNode heroNode2 = new ListNode(2);
        ListNode heroNode3 = new ListNode(3);
        ListNode heroNode4 = new ListNode(4);
        this.add(heroNode1);
        this.add(heroNode2);
        this.add(heroNode3);
        this.add(heroNode4);
        this.getKthFromEndByDoublePoint(head, 1);
    }
}

